package com.yoshino.leetcode.improve40.forth;

class NumMatrix {

    private int[][] preSum;
    public NumMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        // 第一行，第一列都应该为0
        preSum = new int[m][n];
        for (int i = 0; i < m; i++) {
            int pre = 0;
            for (int j = 0; j < n; j++) {
                if (j==0) {
                    preSum[i][j] = matrix[i][j];
                } else {
                    preSum[i][j] = preSum[i][j - 1] + matrix[i][j];
                }
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int res = 0;
        for (int i = row1; i <= row2; i++) {
            if (col1 == 0) {
                res += preSum[i][col2];
            } else {
                res += preSum[i][col2] - preSum[i][col1 - 1];
            }
        }
        return res;
    }
}